#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/**
 *
 *给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。



示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：

输入：triangle = [[-10]]
输出：-10
 *
 *
 *
 * */


//不用说这个题我不会写 dfs也不会写

int minimumTotal(vector<vector<int>> &triangle) {
    //代表 dp最大元素
    vector<vector<int>> dp(triangle.size() + 1, vector<int>(triangle.size() + 1, 0));

    for (int i = triangle.size() - 1; i >= 0; i--) {
        for (int j = 0; j <= i; j++)
            //等于上一行的
            dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
    }

    return dp[0][0];

}


vector<vector<int>> dp;
int n = 0;

//返回最终的结果最小值
//
int dfs(int i, int j, vector<vector<int>> &triangle) {
    if (i == n)
        return 0;
    if (dp[i][j] != INT32_MAX)
        return dp[i][j];
    dp[i][j] = triangle[i][j] + min(dfs(i + 1, j, triangle), dfs(i + 1, j + 1, triangle));
    return dp[i][j];
}

int minimumTotal1(vector<vector<int>> &triangle) {
    n = triangle.size();
    //代表 dp最大元素
    dp.resize(triangle.size() + 1, vector<int>(triangle.size() + 1, INT32_MAX));


    return dfs(0, 0, triangle);

}
